/*
Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


//Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	vector<int> grayCode(int n) {
		vector<int> result;

		result.push_back(0);
		int heightbit = 0;

		while (n--)
		{
			heightbit = result.size();
			for (int i = result.size() - 1; i >=0; i--)
			{
				result.push_back(heightbit | result[i]);
			}
		}

		return result;
	}
};

int main()
{
	cout << "Gray Code :  " << endl;

	int length;
	cout << "Input the n: " << endl;

	cin >> length;

	//vector<int> nums;

	

	Solution s;
	vector<int> result;

	result = s.grayCode(length);

	cout << "The result: " << endl;

	system("pause");

	return 0;
}